НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №4 з навчальної дисципліни “Програмування складних алгоритмів” Тема: Методи пошуку у масивах Варіант 4  Київ 20____ Мета: отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних методів пошуку. Теоретична частина Лінійний пошук Ідея : Проглядати почергово елементи масиву, доки не буде знайдено шуканий елемент або не буде досягнуто кінець масиву. Лінійний пошук з бар'єром Ідея : Як і у попередньому випадку, елементи проглядаються по черзі, але для зменшення кількості порівнянь після останнього елемента додається елемент з ключем, що дорівнює шуканому значенню. Алгоритм Рабіна — Карпа Алгоритм показує високу продуктивність на практиці, а також дозволяє узагальнення на інші споріднені задачі. Ідея алгоритму полягає в заміні текстових рядків числами, порівняння яких можна виконувати значно швидше. Алгоритм полягає в наступному: обчислити число p; обчислити всі  Для тих s для яких виконати перевірку P[1..m] = T[s+1..s+m]. Псевдокод алгоритму / Завдання по варіанту 1. Знайти заданий елемент у невпорядкованому масиві (не менше10х10) за допомогою методу пошуку з бар’єром. 2. Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом / Оцінка складності алгоритму Складність алгоритму пошуку з бар’єром – O(n). Складність алгоритму пошуку Рабіна-Карпа – O(n*m). Спосіб сортування Розмір N*N Час виконання  Пошук з бар’єром 10*10 20мс   50*50 29мс  Пошук методом Рабіна-Карпа 10*10 9мс   50*50 10мс  Результати виконання лабораторної роботи. / Програмний код import java.util.*;public class LR4 { static int iteration1 =0; static int iteration2 =0; public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.print("Введіть розмір масиву: "); int n = scan.nextInt(); int[][] arr = new int[n][n]; for (int i = 0; i < arr.length; i++) for (int j = 0; j < arr.length; j++) arr[i][j] = (int) (Math.random() * 51); System.out.println("Початковий масив для пошуку з бар'єром:"); printArr(arr); System.out.print("Введіть число, яке Ви хочете знайти: "); int num = scan.nextInt(); long firstTime2 = System.currentTimeMillis(); linearSearchWithBarrier(arr, num); firstTime2 = System.currentTimeMillis() - firstTime2; for (int i = 0; i < arr.length; i++) Arrays.sort(arr[i]); System.out.println("\nВідсортований масив для пошуку послідовності алгоритмом Рабіна-Карпа:"); printArr(arr); System.out.print("Введіть кількість чисел у послідовності: "); int amountOfNumbers = scan.nextInt(); int[] sequence = new int[amountOfNumbers]; System.out.print("Введіть послідовність чисел з масиву: "); for (int i = 0; i < amountOfNumbers; i++) { sequence[i] = scan.nextInt(); } long secondTime2 = System.currentTimeMillis(); searchPattern(sequence, arr); secondTime2 = System.currentTimeMillis() - secondTime2; System.out.println("Час виконання пошуку з бар'єром : " + firstTime2 + " мілісекунд."); System.out.println("Час виконання пошуку методом Рабіна-Карпа: " + secondTime2 + " мілісекунд."); } public static void printArr(int[][] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length; j++) { System.out.print(arr[i][j] + "\t"); } System.out.println(); } } public static void linearSearchWithBarrier(int[][] arr, int num) { int temp; int count=0; for (int i = 0; i < arr.length; i++) { ...